package com.algorithm;

import com.google.common.base.Stopwatch;

import java.util.Arrays;
import java.util.concurrent.TimeUnit;

public class Fibonacci {

    public static void main(String[] args) {
        Fibonacci fibonacci = new Fibonacci();
        Stopwatch fibStopWatch = Stopwatch.createUnstarted();
        fibStopWatch.start();
        int result = fibonacci.fib(20);
        fibStopWatch = fibStopWatch.stop();
        System.out.println(result +  " : " + fibStopWatch.elapsed(TimeUnit.MICROSECONDS));
        fibStopWatch.start();
        System.out.println(fibonacci.fibWithMemo(20) + " : " + fibStopWatch.elapsed());
        System.out.println(fibonacci.fibWithDp(20));
        System.out.println(fibonacci.fibWithDpSimple(20));

    }

    /**
     * 功能描述: TODO
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2019-09-16 10:10
     * @modify_auther: kukuxiahuni
     * @modify_time: 2019-09-16 10:10
     **/
    public int fib(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }

    /**
     * 功能描述: TODO
     * @param: 
     * @return: 
     * @auther: kukuxiahuni
     * @date: 2019-09-16 10:18
     * @modify_auther: kukuxiahuni
     * @modify_time: 2019-09-16 10:18
     **/
    public int fibWithMemo(int n) {
        if (n < 1) {
            return 0;
        }

        int[] memo = new int[n+1];
        Arrays.fill(memo, 0);
        memo[1] = memo[2] = 1;
        return helper(memo, n);
    }

    /**
     * 功能描述: TODO
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2019-09-16 10:21
     * @modify_auther: kukuxiahuni
     * @modify_time: 2019-09-16 10:21
     **/
    private int helper(int[] memo, int n) {

        if (n > 0 && memo[n] == 0){
            memo[n] = helper(memo, n - 1) + helper(memo, n - 2);
        }
        return memo[n];
    }

    /**
     * 功能描述: 使用dp表的动态规划
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2019-09-16 10:53
     * @modify_auther: kukuxiahuni
     * @modify_time: 2019-09-16 10:53
     **/
    public int fibWithDp(int n) {

        int[] dp = new int[n + 1];
        dp[1] = dp[2] = 1;
        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    /**
     * 功能描述: TODO
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2019-09-16 10:54
     * @modify_auther: kukuxiahuni
     * @modify_time: 2019-09-16 10:54
     **/
    public int fibWithDpSimple(int n) {
        if (n == 1 || n == 2) {
            return 1;
        }
       int p = 1, pp =1;
        for (int i = 3; i <= n; ++i) {
            int tmp = p + pp;
            p = pp;
            pp = tmp;

        }
        return pp;
    }

}
